package digitRecognitionProblem.learnWeights;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;

import utils.RandomGenerator;

/**
 * Selection is implemented as roulette wheel or tournament.
 * Selection mode is set according to argument to the constructor
 */
public class LWselection extends LW_Selection {

	public static final int ROULETTE = 0;
	public static final int TOURNAMENT = 1;
	private int mode; // selection mode
	private int tournamentSize; // how many chromosomes should include in each round
	
	public LWselection(boolean remove, int mode, int tournamentSize) {
		super(remove);
		this.mode = mode;
		this.tournamentSize = tournamentSize;
	}

	public void setMode(int mode) {
		this.mode = mode;
	}

	public void setTournamentSize(int size) {
		this.tournamentSize = size;
	}
	
	/**
	 * Selects a pair of chromosomes according to roulette wheel selection
	 */
	@Override
	protected Entry<Integer, Integer> selectPair() {
	
		// return parents according to selection type
		switch (mode) {

		case ROULETTE: { // roulette wheel selection
			return rouletteWheel();
		}

		case TOURNAMENT: { // tournament selection
			return tournament();
		}
		
		default: {
			return null;
		}
		}
	}

	private Entry<Integer, Integer> rouletteWheel() {

		// get number of chromosomes in the population
		int numChromosomes = population.getSize();

		/*
		 * initialize look-up table implementing roulette wheel selection:
		 * element's key is chromosome's index in population, value is
		 * chromosome's probability to be chosen (proportional to its fitness)
		 */
		List<Entry<Integer, Double>> lookup = new ArrayList<Entry<Integer, Double>>(
				numChromosomes);

		/*
		 * create entry in lookup table for each chromosome: 
		 * add chromosomes in increasing order of fitness
		 */
		double currFitness = 0.0;
		for (int i = 0; i < numChromosomes; ++i) {

			// calculate fitness for current chromosome
			currFitness = population.getFitnessOfChromosome(i);

			// add chromsome's entry
			lookup.add(new AbstractMap.SimpleEntry<Integer, Double>(i,
					currFitness));
		}

		/*
		 * choose pair of chromosomes (relying on the probabilities): 
		 * choose a number from 0 to total fitness. iterate over lookup table and
		 * accumulate fitness of each chromosome. when reaches a chromosme whose
		 * accumulated value is at least the chosen number, pick this chromosome
		 * and start over again
		 */
		List<Integer> chosen = new ArrayList<Integer>();
		double totalFitness = sumFitness(numChromosomes);
		// keep scanning lookup table until two are chosen
		while (chosen.size() < 2) {

			double accFitness = 0.0; // accumulated fitness

			// choose minimal accumulated fitness value
			double threshold = RandomGenerator.nextInt((int) totalFitness);

			// choose chromosomes according to their probability
			Iterator<Entry<Integer, Double>> itr = lookup.iterator();
			while (itr.hasNext() && (chosen.size() < 2)) {

				// accumulate fitness values
				Entry<Integer, Double> currEntry = itr.next();
				accFitness += currEntry.getValue();

				// check if can choose current chromosome
				if (threshold < accFitness) {

					// add chromosome to return value
					chosen.add(currEntry.getKey());

					// remove from lookup table (parents must be different)
					itr.remove();
				}
			}
		}

		// return indices of parents
		return new AbstractMap.SimpleEntry<Integer, Integer>(chosen.get(0),
				chosen.get(1));
	}

	/**
	 * Returns fitness sum of first to </code> numChromosomes </code>'th
	 * chromosomes in the population 
	 * @param numChromosomes index of last chromosome to consider in the sum
	 * @return sum of indicated chromosomes
	 */
	private double sumFitness(int numChromosomes) {

		double totalFitness = 0.0;
		for (int i = 0; i < numChromosomes; ++i) {
			totalFitness += population.getFitnessOfChromosome(i);
		}
		return totalFitness;
	}

	/**
	 * Selects parents pair according to tournament selection: 
	 * chooses </code> tournamentSize </code> chromosomes from the population, 
	 * and returns best two 
	 * @return indices of chosen chromosomes
	 */
	private Entry<Integer, Integer> tournament() {

		// get number of chromosomes in the population
		int numChromosomes = population.getSize();

		// choose tournament candidates
		List<Entry<Integer, Double>> candidates = new ArrayList<Entry<Integer, Double>>(
				tournamentSize);
		for (int i = 0; i < tournamentSize; ++i) {

			// choose random index for current candidate
			int currCandidate = RandomGenerator.nextInt(numChromosomes);

			// add matching chromosome
			candidates.add(new AbstractMap.SimpleEntry<Integer, Double>(
					currCandidate, population.getFitnessOfChromosome(currCandidate)));
		}

		// sort candidates by their fitness
		Collections.sort(candidates, new Comparator<Entry<Integer, Double>>() {
			public int compare(Entry<Integer, Double> e1,
					Entry<Integer, Double> e2) {

				// compare entries' fitness values
				return e1.getValue().compareTo(e2.getValue());
			}
		});

		// return indices (in population) of two best candidates
		return new AbstractMap.SimpleEntry<Integer, Integer>(candidates.get(0)
				.getKey(), candidates.get(1).getKey());
	}
}
